import java.util.*;

/**
 * @Author 12629
 * @Description：
 */


class Student/* implements Comparable<Student>*/{
    public int age;
    public String name;

    /*@Override
    public int compareTo(Student o) {
        return this.age - o.age;
    }*/

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return age == student.age && Objects.equals(name, student.name);
    }

    @Override
    public String toString() {
        return "Student{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }

    @Override
    public int hashCode() {
        return Objects.hash(age, name);
    }

}

class AgeComparator implements Comparator<Student> {
    @Override
    public int compare(Student o1, Student o2) {
        return o1.age - o2.age;
    }
}

class NameComparator implements Comparator<Student> {
    @Override
    public int compare(Student o1, Student o2) {
        return o2.name.compareTo(o1.name);
    }
}

class Imp implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}


public class Test {


    /**
     * 直接插入排序
     * 最好情况下, 是有序的 时间复杂度为o(n)
     * 最坏情况是 o(n²)
     * @param array
     */
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int j = i - 1;
            int tmp = array[i];
            for (; j >= 0; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                }else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }


    public static void main(String[] args) {
        int[] array = new int[] {80, 70, 60, 839, 4392, 9};
        insertSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static int[] smallestK(int[] array, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Imp());
        for (int i = 0; i < k; i++) {
            maxHeap.offer(array[i]);
        }
        for (int i = k; i < array.length; i++) {
           int top = maxHeap.peek();
           if (top > array[i]) {
               maxHeap.poll();
               maxHeap.offer(array[i]);
           }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = maxHeap.poll();
        }
        return ret;
    }

    /**
     * 找到前k个最小的元素
     * @param array
     * @param k
     * @return
     */
    public static int[] smallestK1(int[] array, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for(int x : array) {
            minHeap.offer(x);
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }



    public static void main5(String[] args) {
        Student s1 = new Student();
        s1.age = 10;
        s1.name = "ahagnsan";

        Student s2 = new Student();
        s2.name = "zhagnsan";
        s2.age = 9;

        AgeComparator ageComparator = new AgeComparator();
        NameComparator nameComparator = new NameComparator();

        PriorityQueue<Student> priorityQueue = new PriorityQueue(nameComparator);
        priorityQueue.offer(s1);
        priorityQueue.offer(s2);
        Student ret = priorityQueue.poll();
        System.out.println(ret);
    }

    public static void main4(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        priorityQueue.offer(11);
        priorityQueue.offer(2);
        priorityQueue.offer(3);

        priorityQueue.poll();
    }


    public static void main3(String[] args) {
        Student s1 = new Student();
        s1.age = 20;
        s1.name = "zhangsan";
        Student s2 = new Student();
        s2.age = 23;
        s2.name = "ahangsan";

        AgeComparator ageComparator = new AgeComparator();
        System.out.println(ageComparator.compare(s1, s2));
        NameComparator nameComparator = new NameComparator();
        System.out.println(nameComparator.compare(s1, s2));
    }
    public static void main2(String[] args) {
        Student s1 = new Student();
        s1.age = 20;
        s1.name = "zhangsan";
        Student s2 = new Student();
        s2.age = 20;
        s2.name = "zhangsan";
        System.out.println(s1.equals(s2));
    }


    public static void testPriority(String[] args) {
        // 创建一个空的优先级队列，底层默认容量是11
        PriorityQueue<Integer> priorityQueue1 = new PriorityQueue();

        // 创建一个空的优先级队列，底层的容量为initialCapacity

        PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(100);

        // 用ArrayList对象来构造一个优先级队列的对象
        List<Integer> list = new ArrayList<>();
        list.add(111);
        list.add(222);
        PriorityQueue<Integer> priorityQueue3 = new PriorityQueue(list);
        priorityQueue2.offer(1);
        priorityQueue2.offer(2);
        priorityQueue2.offer(3);

    }
}